package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/maximum-binary-tree/">最大二叉树(Maximum Binary Tree)</a>
 * <p>给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:<br>
 * 创建一个根节点，其值为 nums 中的最大值。<br>
 * 递归地在最大值 左边 的 子数组前缀上 构建左子树。<br>
 * 递归地在最大值 右边 的 子数组后缀上 构建右子树。<br>
 * 返回 nums 构建的 最大二叉树 。</p>
 * <pre>
 * 示例 1：
 *      输入：nums = [3,2,1,6,0,5]
 *                       6
 *                     /   \
 *                    3     5
 *                     \   /
 *                      2 0
 *                      \
 *                       1
 *      输出：[6,3,5,null,2,0,null,null,1]
 *      解释：递归调用如下所示：
 *          - [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
 *              - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
 *                  - 空数组，无子节点。
 *                  - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
 *                      - 空数组，无子节点。
 *                      - 只有一个元素，所以子节点是一个值为 1 的节点。
 *              - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
 *                  - 只有一个元素，所以子节点是一个值为 0 的节点。
 *                  - 空数组，无子节点。
 *
 * 示例 2：
 *      输入：nums = [3,2,1]
 *                      3
 *                       \
 *                        2
 *                         \
 *                          1
 *      输出：[3,null,2,null,1]
 * </pre>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= nums.length <= 1000</li>
 *     <li>0 <= nums[i] <= 1000</li>
 *     <li>nums 中的所有整数 互不相同</li>
 * </ul>
 *
 * @author c2b
 * @since 2023/5/24 9:23
 */
public class LC0654ConstructMaximumBinaryTree_M {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return buildTree(nums, 0, nums.length - 1);
    }


    public TreeNode buildTree(int[] nums, int leftIndex, int rightIndex) {
        if (leftIndex > rightIndex) {
            return null;
        }
        if (leftIndex == rightIndex) {
            return new TreeNode(nums[leftIndex]);
        }
        // 获取当前数组中最大值所在的索引
        int maxNumIndex = getArrayMaxNumIndex(nums, leftIndex, rightIndex);
        TreeNode root = new TreeNode(nums[maxNumIndex]);
        // 在 [leftIndex,maxNumIndex-1]范围上构建左树
        root.left = buildTree(nums, leftIndex, maxNumIndex - 1);
        // 在 [maxNumIndex+1,rightIndex]范围上构建右树
        root.right = buildTree(nums, maxNumIndex + 1, rightIndex);
        return root;
    }


    /**
     * 获取数组中最大值所在的索引
     *
     * @param nums      数组
     * @param fromIndex 起始位置(包含)
     * @param toIndex   终止位置(包含)
     * @return 最大值所在索引
     */
    private int getArrayMaxNumIndex(int[] nums, int fromIndex, int toIndex) {
        int index = fromIndex;
        int maxNum = nums[fromIndex];
        for (int i = fromIndex + 1; i <= toIndex; i++) {
            if (nums[i] > maxNum) {
                index = i;
                maxNum = nums[i];
            }
        }
        return index;
    }

    public static void main(String[] args) {
        LC0654ConstructMaximumBinaryTree_M lc0654ConstructMaximumBinaryTree_m = new LC0654ConstructMaximumBinaryTree_M();
        //TreeNode node = lc0654ConstructMaximumBinaryTree_m.constructMaximumBinaryTree(new int[]{3, 2, 1, 6, 0, 5});
        TreeNode node = lc0654ConstructMaximumBinaryTree_m.constructMaximumBinaryTree(new int[]{3, 2, 1});
        TreeNode.printTree(node);
    }
}
